package leetcode_1000;

/**
 * @author 周杨
 * 2018年11月19日 下午1:09:53 给定一个数组 问里面有多少个组合 使3个元素加起来等于target
 * Sum3WithMultiplicity_923.java
 * description:常规动态规划 AC 36%
 */
public class Sum3WithMultiplicity_923 {
	public int threeSumMulti(int[] A, int target) {
    	int temp=A[0]+A[1];
		long []dp=new long[target+1];
		if(temp<=target)
			dp[A[0]+A[1]]++;
        long res=0;
        final int MOD=1000000007;
        for(int i=2;i<A.length;++i) {
        	if(A[i]>target)
        		continue;
        	res=(res+dp[target-A[i]])%MOD;
        	for(int j=0;j<i;++j) {
        		 temp=A[j]+A[i];
        		 if(temp<=target) {
        			 dp[temp]++;
        		 }
        	}
        }
        return (int) res;
    }
}
